from typing import List

import copy

# 1. ━   2. ┃
# 3. ┓   4. ┏
# 5. ┛   6. ┗
# 真走一遍，比较啰嗦
class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        point = (0, 0)
        direction = '↑'
        street = grid[0][0]
        if street == 1 or street == 6:
            return self.tryWalk(grid, point, '→')
        elif street == 2 or street == 3:
            return self.tryWalk(grid, point, '↓')
        elif street == 5:
            return False
        else: # street == 4
            leftResult = self.tryWalk(copy.deepcopy(grid), point, '→')
            if leftResult:
                return True
            else:
                return self.tryWalk(grid, point, '↓')

    def tryWalk(self, grid: List[List[int]], p, d) -> bool:
        n = len(grid)
        m = len(grid[0])
        point = p
        direction = d
        while True:
            (x, y) = point
            if x == m - 1 and y == n - 1:
                return True
            street = grid[y][x]
            grid[y][x] = 0 # 表示走过了
            if street == 1:
                if direction == '←':
                    if x == 0:
                        return False # 走到墙边了
                    else:
                        leftPoint = (x - 1, y)
                        leftStreet = grid[y][x - 1]
                        if leftStreet == 4:
                            direction = '↓'
                        elif leftStreet == 6:
                            direction = '↑'
                        elif leftStreet == 1:
                            direction = direction
                        else:
                            return False # 此路不通
                        point = leftPoint
                elif direction == '→':
                    if x == m - 1:
                        return False # 走到墙边了
                    else:
                        rightPoint = (x + 1, y)
                        rightStreet = grid[y][x + 1]
                        if rightStreet == 3:
                            direction = '↓'
                        elif rightStreet == 5:
                            direction = '↑'
                        elif rightStreet == 1:
                            direction = direction
                        else:
                            return False # 此路不通
                        point = rightPoint
                else:
                    raise ValueError("方向不对")
            elif street == 2:
                if direction == '↑':
                    if y == 0:
                        return False # 撞墙了
                    else:
                        topPoint = (x, y - 1)
                        topStreet = grid[y-1][x]
                        if topStreet == 3:
                            direction = '←'
                        elif topStreet == 4:
                            direction = '→'
                        elif topStreet == 2:
                            direction = direction
                        else:
                            return False # 方向不对
                        point = topPoint
                elif direction == '↓':
                    if y == n - 1:
                        return False # 撞墙了
                    else:
                        bottomPoint = (x, y + 1)
                        bottomStreet = grid[y+1][x]
                        if bottomStreet == 5:
                            direction = '←'
                        elif bottomStreet == 6:
                            direction = '→'
                        elif bottomStreet == 2:
                            direction = direction
                        else:
                            return False # 方向不对
                        point = bottomPoint
                else:
                    raise ValueError('方向不对')
            elif street == 3:
                if direction == '↓':
                    if y == n - 1:
                        return False # 撞墙了
                    else:
                        bottomPoint = (x, y + 1)
                        bottomStreet = grid[y+1][x]
                        if bottomStreet == 5:
                            direction = '←'
                        elif bottomStreet == 6:
                            direction = '→'
                        elif bottomStreet == 2:
                            direction = direction
                        else:
                            return False # 方向不对
                        point = bottomPoint
                elif direction == '←':
                    if x == 0:
                        return False # 走到墙边了
                    else:
                        leftPoint = (x - 1, y)
                        leftStreet = grid[y][x - 1]
                        if leftStreet == 4:
                            direction = '↓'
                        elif leftStreet == 6:
                            direction = '↑'
                        elif leftStreet == 1:
                            direction = direction
                        else:
                            return False # 此路不通
                        point = leftPoint
                else:
                    raise ValueError('方向不对')
            elif street == 4:
                if direction == '↓':
                    if y == n - 1:
                        return False # 撞墙了
                    else:
                        bottomPoint = (x, y + 1)
                        bottomStreet = grid[y+1][x]
                        if bottomStreet == 5:
                            direction = '←'
                        elif bottomStreet == 6:
                            direction = '→'
                        elif bottomStreet == 2:
                            direction = direction
                        else:
                            return False # 方向不对
                        point = bottomPoint
                elif direction == '→':
                    if x == m - 1:
                        return False # 走到墙边了
                    else:
                        rightPoint = (x + 1, y)
                        rightStreet = grid[y][x + 1]
                        if rightStreet == 3:
                            direction = '↓'
                        elif rightStreet == 5:
                            direction = '↑'
                        elif rightStreet == 1:
                            direction = direction
                        else:
                            return False # 此路不通
                        point = rightPoint
                else:
                    raise ValueError('方向不对')
            elif street == 5:
                if direction == '←':
                    if x == 0:
                        return False # 走到墙边了
                    else:
                        leftPoint = (x - 1, y)
                        leftStreet = grid[y][x - 1]
                        if leftStreet == 4:
                            direction = '↓'
                        elif leftStreet == 6:
                            direction = '↑'
                        elif leftStreet == 1:
                            direction = direction
                        else:
                            return False # 此路不通
                        point = leftPoint
                elif direction == '↑':
                    if y == 0:
                        return False # 撞墙了
                    else:
                        topPoint = (x, y - 1)
                        topStreet = grid[y-1][x]
                        if topStreet == 3:
                            direction = '←'
                        elif topStreet == 4:
                            direction = '→'
                        elif topStreet == 2:
                            direction = direction
                        else:
                            return False # 方向不对
                        point = topPoint
                else:
                    raise ValueError('方向不对')
            elif street == 6:
                if direction == '→':
                    if x == m - 1:
                        return False # 走到墙边了
                    else:
                        rightPoint = (x + 1, y)
                        rightStreet = grid[y][x + 1]
                        if rightStreet == 3:
                            direction = '↓'
                        elif rightStreet == 5:
                            direction = '↑'
                        elif rightStreet == 1:
                            direction = direction
                        else:
                            return False # 此路不通
                        point = rightPoint
                elif direction == '↑':
                    if y == 0:
                        return False # 撞墙了
                    else:
                        topPoint = (x, y - 1)
                        topStreet = grid[y-1][x]
                        if topStreet == 3:
                            direction = '←'
                        elif topStreet == 4:
                            direction = '→'
                        elif topStreet == 2:
                            direction = direction
                        else:
                            return False # 方向不对
                        point = topPoint
                else:
                    raise ValueError('方向不对')
            else:
                return False # 出现了循环

solu = Solution()
# print(solu.hasValidPath([[2,4,3],[6,5,2]])) # True
# print(solu.hasValidPath([[1,2,1],[1,2,1]])) # False
print(solu.hasValidPath([[4,1],[6,1]])) # False